package problema014;

public class CollatzSequence {
	static int numero;
	static int cant;
	static int[] cache;
	
	public static void main(String[] args){
		//System.out.println(largestCollatz());
		//System.out.println(cache[837799]);
		//largestCollatz();
		//for(int i = 0; i < cache.length; i++) System.out.println(cache[i] + " ");
		System.out.println(l());
	}
	
	public static int l(){
		int mejorPasos = 0, res  = 0;
		for(int i=1; i<=1000000; i+=2){
			int pasos = 1;
			int n = i;
			long act = i;
			while(act!=1){
				if(act % 2 == 0){
					act = act/2;
				}else{
					act = (act*3) + 1;
				}
				pasos++;
			}
			if(pasos > mejorPasos){
				mejorPasos = pasos;
				res = n;
			}
		}
		return res;
	}
	
	public static int largestCollatz(){
		int actual = 0;
		cant = 0;
		cache = new int[1000000]; cache[0] = 1;
		for(int i = 1; i < 1000000; i++) cache[i] = 0;
		for(int i = 1; i <= 1000000; i++){
			actual = contar((long)i,0);
			if(actual >= cant){
				numero = i;
				cant = actual;
			}
		}
		return numero;
		
	}
	
	public static int contar(long num, int cant){
		if(num == 1) return cant;
		if(num > 1000000){
			if(num % 2 == 0){
				return contar(num/2,cant+1);
			}else{
				return contar(3*num+1, cant+1);
			}
		}
		if(num % 2 == 0){			
			if(cache[(int)num-1] != 0){
				return cant + cache[(int)num-1];
			}else{
				cache[(int)num-1] = contar(num/2,cant+1);
				return cache[(int)num-1];
			}
		}else{
			if(cache[(int)num-1] != 0){
				return cant + cache[(int)num-1];
			}else{
				cache[(int)num-1] = contar(3*num +1, cant+1);
				return cache[(int)num-1];
			}	
		}
	}

}
